<!DOCTYPE html>
<html lang="zh-CH" >
<head>
    <meta charset="utf-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <meta name="viewport" content="width=device-width, initial-scale=1" />
    <meta name="author" content="" />
	
	
	
	<title>读书笔记之栈与队列-1 ｜ zansimple</title>
	
    
    
    <meta name="description" content="栈的定义与实现 栈的定义 定义：把运算位置限制在表尾端 栈顶：允许运算端 栈顶指示器：用来指示动态变化的栈顶位置 空栈：表中没有任何元素 满栈：无法申请到栈区可用空间 栈的常见运算：进栈或入栈（表尾插入）、出栈或退栈（表尾删除） 上溢：栈已满还要入栈 下溢：栈已空还要出栈 栈的特性：后进先出
栈的抽象数据类型定义 数据元素：可以是任意的数据，但必须属于同一数据对象。 关系：栈中数据元素之间是线性关系。 基本操作：
 InitStack(S) ClearStack(S) IsEmpty(S) IsFull(S) Push(S , x) Pop(S , x) GetTop(S , x)  栈的顺序实现 定义：
 用一组连续的存储单元依次存放自栈底到栈顶的数据元素. 设一个位置指针top（栈顶指针）动态指示栈顶元素在顺序栈中的位置。 top = -1 表示空栈。  用C语言描述栈的顺序存储结构  #define TRUE 1 #define FALSE 0#define Stack_Size 50//任意长度typedef struct{StackElementType elem[Stack_Size];//类型int top;//指示器}SeqStack;//顺序栈 顺序栈基本操作的实现   初始化
 void InitStack(SeqStack *S){//构造一个空栈S*S-&amp;gt;top = -1;}   判栈空" />
    

    

	
    
    <link rel="shortcut icon" href="https://lenzan.github.io/images/favicon.ico" />

    <link rel="stylesheet" type="text/css" media="screen" href="https://lenzan.github.io/css/normalize.css" />
    <link rel="stylesheet" type="text/css" media="screen" href="https://cdn.jsdelivr.net/npm/animate.css@4.1.0/animate.min.css" />
    <link rel="stylesheet" type="text/css" media="screen" href="https://lenzan.github.io/css/zozo.css" />
	<link rel="stylesheet" type="text/css" media="screen" href="https://cdn.jsdelivr.net/npm/remixicon@2.5.0/fonts/remixicon.css" />
    <link rel="stylesheet" type="text/css" media="screen" href="https://lenzan.github.io/css/highlight.css" />

    
    
</head>

<body>
    <div class="main animate__animated animate__fadeInDown">
        <div class="nav_container animated fadeInDown">
    <div class="site_nav" id="site_nav">
        <ul>
            
            <li>
                <a href="/">首页</a>
            </li>
            
            <li>
                <a href="/">unity</a>
            </li>
            
            <li>
                <a href="/">归档</a>
            </li>
            
            <li>
                <a href="/">关于</a>
            </li>
            
        </ul>
    </div>
    <div class="menu_icon">
        <a id="menu_icon"><i class="ri-menu-line"></i></a>
    </div>
</div>
        <div class="header animated fadeInDown">
    <div class="site_title_container">
        <div class="site_title">
            <h1>
                <a href="https://lenzan.github.io/">
                    <span>zansimple</span>
                    <img src="https://lenzan.github.io/images/logo.svg" />
                </a>
            </h1>
        </div>
        <div class="description">
            <p class="sub_title">专注于Unity虚拟现实开发，游戏开发</p>
            <div class="my_socials">
                
                <a href="https://lenzan.github.io/index.xml" type="application/rss+xml" title="rss" target="_blank"><i
                        class="ri-rss-fill"></i></a>
            </div>
        </div>
    </div>
</div>
        <div class="content">
            <div class="post_page">
                <div class="post animate__animated animate__fadeInDown">
                    <div class="post_title post_detail_title">
                        <h2><a href='/posts/data/stackandQueue/'>读书笔记之栈与队列-1</a></h2>
                        <span class="date">2018.06.24</span>
                    </div>
                    <div class="post_content markdown"><h2 id="栈的定义与实现">栈的定义与实现</h2>
<h3 id="栈的定义">栈的定义</h3>
<p>定义：把运算位置限制在表尾端
栈顶：允许运算端
栈顶指示器：用来指示动态变化的栈顶位置
空栈：表中没有任何元素
满栈：无法申请到栈区可用空间
栈的常见运算：进栈或入栈（表尾插入）、出栈或退栈（表尾删除）
上溢：栈已满还要入栈
下溢：栈已空还要出栈
栈的特性：后进先出<br>
<img src="/img/stack/stack1.jpg" alt="stack"></p>
<h4 id="栈的抽象数据类型定义">栈的抽象数据类型定义</h4>
<p>数据元素：可以是任意的数据，但必须属于同一数据对象。
关系：栈中数据元素之间是线性关系。
基本操作：</p>
<ul>
<li>InitStack(S)</li>
<li>ClearStack(S)</li>
<li>IsEmpty(S)</li>
<li>IsFull(S)</li>
<li>Push(S , x)</li>
<li>Pop(S , x)</li>
<li>GetTop(S , x)</li>
</ul>
<h3 id="栈的顺序实现">栈的顺序实现</h3>
<p>定义：</p>
<ul>
<li>用一组连续的存储单元依次存放自栈底到栈顶的数据元素.</li>
<li>设一个位置指针top（栈顶指针）动态指示栈顶元素在顺序栈中的位置。</li>
<li>top = -1 表示空栈。</li>
</ul>
<h4 id="用c语言描述栈的顺序存储结构">用C语言描述栈的顺序存储结构</h4>
<pre><code>    #define TRUE 1  
    #define FALSE 0
    #define Stack_Size 50//任意长度
    typedef struct
    {
        StackElementType elem[Stack_Size];//类型
        int top;//指示器
    }SeqStack;//顺序栈
</code></pre>
<h4 id="顺序栈基本操作的实现">顺序栈基本操作的实现</h4>
<ul>
<li>
<p>初始化</p>
<pre><code>  void InitStack(SeqStack *S)
  {
      //构造一个空栈S*
      S-&gt;top = -1;
  }
</code></pre>
</li>
<li>
<p>判栈空</p>
<pre><code>  int IsEmpty(SeqStack *S){
      //判栈S为空栈时返回值为真，反之为假
      return(S-&gt;top == -1 ? TRUE : FALSE);
  }
</code></pre>
</li>
<li>
<p>判栈满</p>
<pre><code>  int IsFull(SeqStack *S){
      //判栈S为满时返回值为真，反之为假
      return(S-&gt;top == Stack_Size - 1 ? TRUE : FALSE);
  }
</code></pre>
</li>
<li>
<p>进栈</p>
<pre><code>  int Push(SeqStack *S , StackElementType x){
      if(S-&gt;top == Stack_Size - 1)//判断栈是否已满
      return(FALSE);
      S-&gt;top++;
      S-&gt;elem[S-&gt;top] = x;
      return(TURE);
  }
</code></pre>
</li>
<li>
<p>出栈</p>
<pre><code>  int Pop(SeqStack *S , StackElementType *x){
      if(S-&gt;top == - 1){
          //判断栈是否已空
      return(FALSE);
      }
      else{
          *x =S-&gt;elem[S-&gt;top];
           S-&gt;top--;
          return(TURE);
      }
  }
</code></pre>
</li>
<li>
<p>读栈顶元素</p>
<pre><code>   int GetTop(SeqStack *S , StackElementType *x){
      if(S-&gt;top == - 1){
          //判断栈是否已空
      return(FALSE);
      }
      else{
          *x =S-&gt;elem[S-&gt;top];
          return(TURE);
      }
  }
</code></pre>
</li>
</ul>
<h4 id="两栈共享的数据结构">两栈共享的数据结构</h4>
<h5 id="两栈共享栈空间示意图">两栈共享栈空间示意图</h5>
<p>利用了栈栈底位置不变 ， 而栈顶位置动态变化的特性为两个栈申请一个共享的一维数组空间S[M]<br>
将两个栈的栈底分别为一维数组的两端 0 和 M-1<br>
共享栈空间示意： top[0] 和 top[1] 为两个栈顶指示器</p>
<h5 id="两栈共享的数据结构定义">两栈共享的数据结构定义</h5>
<pre><code>    #define M 100
    typedef struct{
        StackElementType Stack[M];//栈区
        int top[2];//两个栈顶指示器
    }DqStack;
</code></pre>
<h5 id="初始化操作算法">初始化操作算法</h5>
<pre><code>    void InitStack(DqStack *S){
        S-&gt;top[0] = -1;
        S-&gt;top[1] = M;
    }
</code></pre>
<h5 id="进栈操作算法">进栈操作算法</h5>
<p>进栈操作步骤：</p>
<ul>
<li>
<p>进栈需判栈满 S-&gt;top[0] + 1 == S-&gt;top[1]</p>
</li>
<li>
<p>修改栈顶指针</p>
</li>
<li>
<p>元素进栈</p>
<pre><code>  int Push(DqStack *S , StackElementType x , int i){
      if(S-&gt;top[0] + 1 == S-&gt;top[1])//判断栈是否已满
      return(FALSE);
      switch(i){
          case 0:
              S-&gt;top[0]++;
              S-&gt;Stack[S-&gt;top[0]] = x;
              break;
          case 1:
              S-&gt;top[1]--;
              S-&gt;Stack[S-&gt;top[1]] = x;
              break;
          default:
          return(FALSE);
     }
     return(TRUE)
  }
</code></pre>
</li>
</ul>
<p><img src="/img/stack/stack3.jpg" alt="stack2"></p>
<h5 id="出栈操作算法">出栈操作算法</h5>
<p>出栈操作步骤：</p>
<ul>
<li>
<p>出栈需判空</p>
</li>
<li>
<p>元素出栈</p>
</li>
<li>
<p>修改栈顶指针</p>
<pre><code>  int Pop(DqStack *S , StackElementType *x , int i){
      switch(i){
          case 0:
              if(S-&gt;top[0] == -1)return(FALSE);
              *x = S-&gt;Stack[S-&gt;top[0]];
              S-&gt;top[0]--;
              break;
          case 1:
              if(S-&gt;top[1] == M)
              return(FALSE);
              *x = S-&gt;Stack[S-&gt;top[1]];
              S-&gt;top[1]++;
              break;
          default:
          return(FALSE);
     }
     return(TRUE)
  }
</code></pre>
</li>
</ul>
<h3 id="栈的链式实现">栈的链式实现</h3>
<h4 id="链栈的定义及示意图">链栈的定义及示意图</h4>
<p>采用带头结点的单链表实现链栈。<br>
头指针就作为指针<br>
链栈示意图:<br>
<img src="/img/stack/stack4.jpg" alt="链栈"></p>
<ul>
<li>top 为栈顶指针，始终指向当前栈顶元素前面的头结点。</li>
<li>若 top -&gt; next == NULL , 则代表空栈</li>
</ul>
<h4 id="用c语言定义的链栈结构">用C语言定义的链栈结构</h4>
<pre><code>    typedef struct node{
        StackElementType data;
        struct node *next;
    }LinkStackNode;
    typedef LinkStackNode *LinkStack;
</code></pre>
<h4 id="链栈的进栈操作">链栈的进栈操作</h4>
<pre><code>    int Push(LinkStacktop , StackElementType x){
        LinkStackNode* temp;//将数据元素x压人栈 top 中
        temp = (LinkStackNode*)malloc(sizeof(LinkStackNode));
        if(temp == NULL)return(FALSE);//申请空间失败
        temp-&gt;data = x;
        temp-&gt;next = top-&gt;next;
        top-&gt;next = temp;//修改当前栈顶指针
        return(TRUE);
    }
</code></pre>
<h4 id="链栈的出栈操作">链栈的出栈操作</h4>
<pre><code>    int Pop(LinkStacktop , StackElementType *x){
        LinkStackNode* temp;//将栈 top 的栈顶元素弹出，放到x所指的存储空间中
        temp = top-&gt;next;
        if(temp == NULL)return(FALSE);//栈为空
        top-&gt;next = temp-&gt;next;
        *x = temp-&gt;data;
        free(temp);//释放存储空间
        return(TRUE);
    }
</code></pre>
<h4 id="多栈运算">多栈运算</h4>
<h2 id="栈的应用与递归">栈的应用与递归</h2>
<h3 id="括号匹配">括号匹配</h3>
<p>算法思想：利用设置一个括号栈判别左右括号个数与类型匹配的情况</p>
<ul>
<li>若读入左括号则入栈，等带相匹配的同类右括号</li>
<li>若读入右括号且与栈顶的左括号类型匹配，栈顶左括号出栈，否则属于不合法</li>
</ul>
<h3 id="表达式求值">表达式求值</h3>
<ul>
<li>
<p>无括号算术表达式求值</p>
<pre><code>  运算符优先级
  #  +-  */  **
  0   1   2   3
</code></pre>
</li>
<li>
<p>算术表达式处理规则</p>
<ol>
<li>规定运算符的优先级表</li>
<li>设置两个栈：OVS（运算数栈）、OPTR（运算符栈）</li>
<li>自左向右扫描，进行如下处理</li>
</ol>
<ul>
<li>遇到 运算数则进 OVS 栈</li>
<li>遇到运算符则与 OPTR 栈的栈顶运算符进行优先级比较：
如果当前运算符 &gt;OPTR 栈顶运算符，则当前运算符进 OPTR 栈
如果当前运算符&lt;=OPTR 栈顶运算符，则 OPTR 退栈一次，得到栈顶运算符 y, OVS 连续退栈两次，得到运算数 a,b,对 a,b 执行 y 操作，得到结果 T(i) ,将 T(i) 进 VOS 栈。</li>
</ul>
</li>
</ul>
<h3 id="栈与递">栈与递</h3>
<p>递归：在定义自身的同时又出现了对自身的调用。
直接递归函数:在定义的函数体内直接调用自己。
间接递归函数：一个函数经过一系列中间调用语句，通过其他函数简介调用自己，如 P 调用 Q ，Q 在调用 P。</p>
<h4 id="递归特性的问题">递归特性的问题</h4>
<h5 id="递归定义的数学函数">递归定义的数学函数</h5>
<ul>
<li>
<p>二阶Fibonacci数列</p>
<pre><code>  int Fib(int n){
      if(n == 0)
      return 0;
      if(n == 1)
      return 1 ;
      return Fib(n-1) + Fib(n-2);
  }
</code></pre>
</li>
<li>
<p>阿克曼函数</p>
<pre><code>  int Ack(int m , int n){
      if(m == 0)
      return n+1;
      else if(m != 0 &amp;&amp; n == 0)
      return Ack(m-1 , 1);
      else
      return Ack(m-1 , Ack(m , n-1));
  }
</code></pre>
</li>
</ul>
<h5 id="递归数据结构的处理">递归数据结构的处理</h5>
<p>如：广义表、二叉树、树等结构其本身均具有固有的递归特性，因此可以自然地采用递归法进行处理。</p>
<h5 id="递归求解方法">递归求解方法</h5>
<p>例子：汉诺塔问题的算法实现</p>
<pre><code>    //将塔座X上编号为1至 n 的 n 个由小到大圆盘按规则搬到塔座 Z 上，Y 可用作辅助塔座
    void hanoi(int n , char y , char z){
        if(n == 1){
            move(x,1,z)//将编号为1的圆盘从 X 移动到 Z
        }
        else{
            hanoi(n-1 , x , z , y);//将 X 上编号为 1 至 n-1 的圆盘移到 Y,Z 作辅助塔
            move(x , n , z);//将编号为 n 的圆盘从 X 移动到 Z
            hanoi(n-1 , y , x , z);//将 y 上编号为1至 n-1 的圆盘移动到 z , x作辅助塔
        }
        
    }
</code></pre>
<h5 id="递归问题的优点">递归问题的优点</h5>
<ul>
<li>对递归问题描述简洁</li>
<li>结构清晰</li>
<li>程序的正确性容易证明</li>
</ul>
</div>
                    <div class="post_footer">
                        
                        <div class="meta">
                            <div class="info">
                                <span class="field tags">
                                    <i class="ri-stack-line"></i>
                                    
                                    <a href="https://lenzan.github.io/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>
                                    
                                </span>
                            </div>
                        </div>
                        
                    </div>
                </div>
                
                
            </div>
        </div>
    </div>
    <a id="back_to_top" href="#" class="back_to_top"><span>△</span></a>
    <footer class="footer">
    <div class="powered_by">
        <a href="https://varkai.com">Designed by VarKai,</a>
        <a href="http://www.gohugo.io/">Proudly published with Hugo</a>
    </div>

    <div class="footer_slogan">
        <span></span>
    </div>
</footer>
    <script src="https://lenzan.github.io/js/jquery-3.5.1.min.js"></script>
<link href="https://lenzan.github.io/css/fancybox.min.css" rel="stylesheet">
<script src="https://lenzan.github.io/js/fancybox.min.js"></script>
<script src="https://lenzan.github.io/js/zozo.js"></script>






</body>

</html>